package com.zlsy.learning.leetcode.sort;

import java.util.Arrays;

/**
 * @author zhouliang
 * @date 2020/9/1 20:09
 */
public class QuickSort {

  public static void main(String[] args) {
    //    int[] a = new int[] {6, 11, 3, 9, 8};
    int[] a = new int[] {6, 11, 3, 9, 7, 8, 10};
    int n = a.length;
    quickSort(a, n);
    System.out.println(Arrays.toString(a));
  }
  /**
   * 快速排序，a是数组，n表示数组的大小
   *
   * @param a a是数组
   * @param n n数组的大小
   */
  public static void quickSort(int[] a, int n) {
    quickSortInternally(a, 0, n - 1);
  }

  /**
   * 快速排序递归函数，p,r为下标
   *
   * @param a
   * @param p
   * @param r
   */
  private static void quickSortInternally(int[] a, int p, int r) {
    if (p >= r) {
      return;
    }
    // 先获取分区点，比它小的放左边，比它大的放右边
    int q = partition(a, p, r);
    // 递归处理，一直处理上段代码，分解为1的时候即完成
    quickSortInternally(a, p, q - 1);
    quickSortInternally(a, q + 1, r);
  }

  /**
   * 1、取最后一位作为分区点；把比这个分区点小的放左边，把比这个分区点大的放右边 2、返回这个分区点
   *
   * @param a
   * @param p
   * @param r
   * @return
   */
  private static int partition(int[] a, int p, int r) {
    int i = p;
    int pivot = a[r];
    for (int j = p; j < r; j++) {
      // 如果当前处理为小于中区点才进行处理
      if (a[j] < pivot) {
        // i和j处于同一个位置，i和j都进位
        if (i == j) {
          i++;
        } else {
          int temp = a[i];
          // i和j交换位置，且i进位
          a[i++] = a[j];
          a[j] = temp;
        }
      }
    }

    // 当j=r时候,i的位置即为中区点
    int temp = a[i];
    // 把中区点放在属于它的位置
    a[i] = a[r];
    a[r] = temp;

    return i;
  }
}
